The performance of a computer system largely depends on the performance of its slowest component. For example, retrieving data from a non-volatile storage device, such as one or more hard disk drives, to a high-speed memory, is limited by the speed of the disk drives. Various techniques are used to improve performance. One such technique is known as “caching,” in which data retrieved from disk are retained in the high-speed memory in order to improve the access time for that data on subsequent accesses. Another technique is known as “prefetching,” in which data are retrieved from disk in advance of an explicit request for the data, in order to have the data available in high-speed memory at the time the request is made. Still another technique is the reordering of input from and output to the disk, when feasible. For example, a disk with a queue of several blocks to write might reorder the write operations to minimize the latency of repositioning a disk head between writes.
During a sequential read operation, an application program, such as a restore program, will process numerous data records stored at contiguous locations in the storage device. It is desirable during such sequential read operations to prefetch the sequential data into cache in anticipation of the requests from the application program. A sequential caching algorithm detects when a device is requesting data as part of a sequential access operation. Upon making such detection, the storage controller or server may begin prefetching sequential data records following the last requested data record into a cache in anticipation of future sequential accesses. The cached records may then be returned to the application performing the sequential data operations at speeds substantially faster than retrieving the records from a non-volatile storage device.
The field of deduplicating storage systems adds a layer of complexity to the problem of improving read performance. In a deduplicating storage system, unique pieces of data known as “chunks” or “data chunks” are identified via hashes known as “fingerprints.” In this specification, chunks and data chunks are used interchangeably. To read back a file, the system loads a list of fingerprints for the file, and then reads the chunks corresponding to the fingerprints. One method for finding the chunks on disk is to have an index that associates a fingerprint with a container, which is an aggregate of many chunks. These chunks can be concatenated together and compressed to save disk space beyond the benefits that deduplication provides. Once identifying the correct container, the file system can load the metadata for the container, which lists all the fingerprints of the chunks stored in the container, along with their locations. To read a particular chunk, the system reads a read unit (RU) such as a compression region (CR) containing the chunk desired. At this point other chunks in that RU are also loaded into memory, because the RU is the unit of an input/output (IO) operation when reading from the disk. In contrast, when writing to the disk, a full container is written in one IO operation.
Once read into memory, the RU can be retained in a cache to improve the performance of later accesses to chunks in the RU. The system reserves some amount of memory as a cache for RUs, and whenever a new one is loaded into memory, another RU must be removed from the cache when the cache space is insufficient. A typical paradigm is to cache data in a “least recently used” (LRU) fashion, using past accesses as a prediction of future behavior. Often such a prediction is inaccurate and unreliable, particularly, for a backup storage system. LRU works well on data with good locality (e.g., stored in nearby locations); it does not work as well with fragmented storage locations such as would be found in a deduplicated storage system. In a backup storage system, especially a deduplicating backup storage, files are chunked and chunks are stored across multiple different storage locations or containers. Further, after the incremental backup and/or garbage collection, the chunks of the files are dispersed within the storage system and the locality tends to worsen.
When reading back a deduplicated file, two things are different from “traditional” file systems that have used LRU caching effectively for many decades. Firstly, deduplicated data can be fragmented among many different places on a disk. In a standard file system, when writing a file, the entire file is typically written contiguously in the file system, and a single large read is sufficient to provide the file to a reader. In a deduplicating system, a file may consist of references to many different containers because versions of the file have been created over time. Secondly, restoring backup data may result in an extremely large read request, which provides information in advance about all the fingerprints that will be needed over an extended period of input/output (IO) transactions. The quantity of “look-ahead” information available may be substantially greater than in a traditional system. Given the differences, it is desirable to analyze the order of chunks in a file before servicing a request to read the file.